package arrays;

import java.util.Stack;

//双指针,快慢指针
public class Solution_2 {

    /**
     * 844. 比较含退格的字符串
     * @param s
     * @param t
     * @return
     * 思路:非退格#，就是有效元素，如果#，就删除前一个有效元素，如果#前面没有有效元素，
     * 一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。
     * 还可以用栈来解决 有效元素进栈，如果栈内有元素，遇到退格符号#，就出栈
     */
    public boolean backspaceCompare(String s, String t) {
        return build(s).equals(build(t));

    }
    public String build(String str) {
        StringBuffer ret = new StringBuffer();
        int length = str.length();
        for (int i = 0; i < length; i++) {
            char ch = str.charAt(i);
            if (ch != '#') {
                ret.append(ch);
            } else {
                if (ret.length() > 0) {
                    ret.deleteCharAt(ret.length() - 1);
                }
            }
        }
        return ret.toString();
    }

    private String processString(String str) {
        Stack<Character> stack = new Stack<>();
        for (char ch : str.toCharArray()) {
            if (ch != '#') {
                stack.push(ch);
            } else if (!stack.isEmpty()) {
                stack.pop();
            }
        }
         return stack.toString();
    }

    /**
     * 977. 有序数组的平方 - 双指针
     * @param nums
     * @return
     */
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int index = nums.length - 1;
        while (left <= right) {
            if(nums[left] * nums[left] > nums[right] * nums[right]) {
                result[index--] = nums[left] * nums[left];
                left ++;
            } else {
                result[index--] = nums[right] * nums[right];
                right --;
            }
        }
        return result;
    }

    /**
     * 209. 长度最小的子数组 -middle
     * 滑动窗口 ：不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果
     * 这里是：据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int result = Integer.MAX_VALUE; //初始结果为最大值，才能找最小的子数组
        int sum = 0;
        for(;right < nums.length;right++) {
            sum += nums[right];
            //当窗口内的和大于等于target时，缩小窗口，这里即缩小左边界
            while(sum >= target) {
                int len = right - left + 1;
                result = Math.min(len, result);
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;

    }

    /**
     * 59. 螺旋矩阵 II
     * @param n
     * @return
     */
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int left = 0, right = n - 1;
        int top = 0, bottom = n - 1;
        int num = 1;
        //顺时针填充 直到n*n
        while (num <= n * n) {
            //从左往右
            for (int i = left; i <= right; i++) {
                result[top][i] = num++;
            }
            //上边界填充完,top 边界向下移动
            top++;
            //从上往下
            for (int i = top; i <= bottom; i++) {
                result[i][right] = num++;
            }
            //右边界填充完，right边界向左移动
            right--;
            //从右往左
            for (int i = right; i >= left; i--) {
                result[bottom][i] = num++;
            }
            //下边界填充完，bottom边界向上移动
            bottom--;
            for (int i = bottom; i >= top; i--) {
                result[i][left] = num++;
            }
            left++;
        }
        return result;
    }


}
